class Solution:
    def numSubmat(self, mat: list) -> int:
        dp = [[0 for _ in range(len(mat[i]))] for i in range(len(mat))]
        oneIndexes = []
        for j in range(len(mat[0])):
            ones = 0
            for i in range(len(mat)):
                if mat[i][j] == 1:
                    ones += 1
                    oneIndexes.append((i, j))
                else:
                    ones = 0
                dp[i][j] = ones
        res = 0
        for i, j in oneIndexes:
            minLength = dp[i][j]
            for n in range(j, -1, -1):
                if dp[i][n] == 0:
                    break
                minLength = min(minLength, dp[i][n])
                res += minLength

        return res
